package com.lft.sort05.quick_sort;

import java.util.Arrays;

/**
 * 【快速排序】
 */
public class QuickSort {
	public static void main(String[] args) {
		int[] a = {-9, 78, 0, 23, -567, 70};
		System.out.println(Arrays.toString(quickSort(a, 0, a.length - 1)));
	}
	
	public static int[] quickSort(int[] a, int left, int right) {
		int l = left;
		int r = right;
		// 中轴
		int pivot = a[(left + right) / 2];
		// 临时变量，作为交换时使用。
		int temp;
		// while 循环的目的是让比 pivot 值小放到左边。
		// 比 pivot 值大的放到右边。
		while (l < r) {
			// 在 pivot 的左边一直找，找到大于等于 pivot 值，才退出
			while (a[l] < pivot) {
				l += 1;
			}
			// 在 pivot 的右边一直找，找到小于等于 pivot 值，才退出
			while (a[r] > pivot) {
				r -= 1;
			}
			// 如果 l >= r 说明 pivot 的左右两边的值，已经按照左边全是小于等于 pivot，右边全是大于等于 pivot
			if (l >= r) {
				break;
			}
			// 交换
			temp = a[l];
			a[l] = a[r];
			a[r] = temp;
			
			// 如果交换完后，发现这个 a[l] == pivot 值，则 r--，前移。
			if (a[l] == pivot) {
				r -= 1;
			}
			// 如果交换完后，发现这个 a[r] == pivot 值，则 l++，后移。
			if (a[r] == pivot) {
				l += 1;
			}
		}
		// 如果 l == r，必须 l++,r--，否则会出现栈溢出。
		if (l == r) {
			l += 1;
			r -= 1;
		}
		// 向左递归
		if (left < r) {
			quickSort(a, left, r);
		}
		// 向右递归
		if (right > l) {
			quickSort(a, l, right);
		}
		return a;
	}
}
